package com.cat.chapter036;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author cat
 * @description https://leetcode.cn/problems/maximum-width-of-binary-tree/
 * @create 2025/6/14 20:15
 * @since JDK17
 */
// 其实题目中的树可以看作是一颗满的二叉树
public class Solution03 {
    static final int MAXN = 3001;
    TreeNode[] queue = new TreeNode[MAXN];
    int l = 0;
    int r = 0;
    int ans = 0;
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        queue[r++] = root;  // 将根节点压入队列
        root.val = 1;
        ans = Math.max(queue[r - 1].val - queue[l].val + 1, ans);
        while (l < r) {
            int j = r;
            while (l < j) { // 一次处理一层
                TreeNode node = queue[l++];
                if (node.left != null) {
                    queue[r++] = node.left;
                    node.left.val = node.val * 2;
                }
                if (node.right != null) {
                    queue[r++] = node.right;
                    node.right.val = node.val * 2 + 1;
                }
            }
        }
        return ans;
    }
}
